package cn.algorithm.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 *
 * @author dunlingiz
 * @date 2024/2/29
 * @since v
 */
public class BubbSort {

    /**
     * 基础 将数组元素两两比较，大的元素往后进行交换
     * 例子： [3, 4, 2, 1, 5, 6, 7, 8]
     * 第一轮次：[3, 2, 1, 4, 5, 6, 7, 8]
     * 第二轮次：[2, 1, 3, 4, 5, 6, 7, 8]
     * 第三轮次：[1, 2, 3, 4, 5, 6, 7, 8]
     * 第四轮次：[1, 2, 3, 4, 5, 6, 7, 8]
     * 第五轮次：[1, 2, 3, 4, 5, 6, 7, 8]
     * 第六轮次：[1, 2, 3, 4, 5, 6, 7, 8]
     * 第七轮次：[1, 2, 3, 4, 5, 6, 7, 8]
     */
    public static void basis(int[] array) {
        System.out.println("数组：" + Arrays.toString(array));
        int arrLen = array.length - 1;
        for (int i = 0; i < arrLen; i++) {
            // 每次两两比较都会将最大的元素移植末尾，故下一个轮次末尾元素就无需参与比较了
            int length = array.length - i - 1;
            for (int j = 0; j < length; j++) {
                int temp;
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
            System.out.println("排序第" + (i + 1) + "轮");
            System.out.println(Arrays.toString(array));
        }
    }

    /**
     * 优化冒泡排序:排序元素已经是顺序的了，要提前进行跳出，避免无效的计算
     * 例子： [3, 4, 2, 1, 5, 6, 7, 8]
     * * 第一轮次：[3, 2, 1, 4, 5, 6, 7, 8]
     * * 第二轮次：[2, 1, 3, 4, 5, 6, 7, 8]
     * * 第三轮次：[1, 2, 3, 4, 5, 6, 7, 8] ==> 本轮次确定数组元素已经是顺序的了，顺序标志
     * * 第四轮次：[1, 2, 3, 4, 5, 6, 7, 8] ==> 本轮次交换结束，查看顺序标志
     *
     * @param array
     */
    public static void optimSort(int[] array) {
        System.out.println("数组：" + Arrays.toString(array));
        int arrLen = array.length - 1;
        for (int i = 0; i < arrLen; i++) {
            // 当出现一个轮次中没有进行交换的操作，就可以判断元素已经是顺序的了，再次执行下一个轮次之后就直接跳出循环
            boolean isSorted = true;
            // array.length - i - 1  =>
            int length = array.length - i - 1;
            for (int j = 0; j < length; j++) {
                int temp = 0;
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    isSorted = false;
                }
            }
            System.out.println("排序第" + (i + 1) + "轮");
            System.out.println(Arrays.toString(array));
            if (isSorted) {
                break;
            }
        }
    }

    /**
     * 优化冒泡排序
     * 思考：将每一轮次的最后一次交换的元素作为分界点，将数组分为有序部分和无序部分，下一个轮次只需比较无序部分即可
     *
     * @param array
     */
    public static void orderSort(int[] array) {
        System.out.println("数组：" + Arrays.toString(array));
        int arrLen = array.length - 1;
        int lastExchange = 0;
        int sortBord = arrLen;
        for (int i = 0; i < arrLen; i++) {
            // 当出现一个轮次中没有进行交换的操作，就可以判断元素已经是顺序的了，再次执行下一个轮次之后就直接跳出循环
            boolean isSorted = true;
            // 最后一轮由于sortBord，并没有进行比较交换
            for (int j = 0; j < sortBord; j++) {
                int temp = 0;
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    isSorted = false;
                    lastExchange = j;
                }
            }
            System.out.println("排序第" + (i + 1) + "轮");
            System.out.println(Arrays.toString(array));
            sortBord = lastExchange;
            if (isSorted) {
                break;
            }
        }
    }

    /**
     * 鸡尾酒排序：主要解决数组大部分元素已经是顺序的情况
     * 双向的进行交换，先从左到右进行比较交换，再从右到左进行比较交换，类似钟摆一样
     * [2, 1, 3, 4, 8, 6, 7, 5] => 正序[1,2,3,4,6,7,5,8] => 逆序[1,2,3,4,5,6,7,8]   第一轮
     * 第二轮 正序[1,2,3,4,6,7,5,8]
     */
    public static void cocktailSort(int[] array) {
        int temp;
        // 循环列表，每次进行来回摆动比对交换，故只需要循环数列长度的一半即可
        for (int i = 0; i < array.length / 2; i++) {
            // 数列顺序标识
            boolean isSorted = true;
            int length = array.length - i - 1;
            // 正循环比对，将数列最大值交换到数列末尾
            for (int j = 0; j < length; j++) {
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    isSorted = false;
                }
            }
            System.out.println("正序排序第" + (i + 1) + "轮");
            System.out.println(Arrays.toString(array));
            if (isSorted) {
                break;
            }
            isSorted = true;
            //逆循环比对，将数列最小值交换到数列头部
            for (int j = length; j > 0; j--) {
                if (array[j] < array[j - 1]) {
                    temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                    isSorted = false;
                }
            }
            System.out.println("逆序排序第" + (i + 1) + "轮");
            System.out.println(Arrays.toString(array));
            if (isSorted) {
                break;
            }
        }
    }

    /**
     * 优化 鸡尾酒排序
     */
    public static void cocktailSortOptimize(int[] array) {
        int temp;
        //右边有序无序分界点，无序参与下一轮次对比交换的数列
        int rightSortBord = array.length - 1;
        //左边有序无序分界点，无序参与下一轮次对比交换的数列
        int leftSortBord = 0;
        int lastExchange = 0;
        for (int i = 0; i < array.length / 2; i++) {
            boolean isSorted = true;
            // 奇数轮进行正循环比对
            for (int j = leftSortBord; j < rightSortBord; j++) {
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    isSorted = false;
                    lastExchange = j;
                }
            }
            System.out.println("正序排序第" + (i + 1) + "轮");
            System.out.println(Arrays.toString(array));
            rightSortBord = lastExchange;
            if (isSorted) {
                break;
            }
            isSorted = true;
            //偶数轮进行逆循环比对
            for (int j = rightSortBord; j > leftSortBord; j--) {
                if (array[j] < array[j - 1]) {
                    temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                    isSorted = false;
                    lastExchange = j;
                }
            }
            System.out.println("逆序排序第" + (i + 1) + "轮");
            System.out.println(Arrays.toString(array));
            leftSortBord = lastExchange;
            if (isSorted) {
                break;
            }
        }
    }
}
